package main

import (
	"data-structure/sortedList"
	"fmt"
)

func main() {
	nums := []int{56, 1, 22, 23, 54, 16, 17, 9, 34}
	bucketSort(nums)
	fmt.Println(nums)
}

//golang这里我采用有序链表作为桶容器
func bucketSort(nums []int) {
	min, max := nums[0], nums[0]
	for _, v := range nums {
		if v < min {
			min = v
		}
		if v > max {
			max = v
		}
	}
	bucketSize := (max-min)/len(nums) + 1
	buckets := make([]sortedList.List, bucketSize)
	for _, v := range nums {
		buckets[((v - min) / len(nums))].Insert(v)
	}
	index := 0
	for _, v := range buckets {
		for ; v.Len > 0; index++ {
			nums[index] = v.PopFront()
		}
	}
}

//@TODO: 排序暂时到此为止, 开启图论章节, 后面可能会接触 基数排序, 平滑排序,
